package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname HouseRobber
 * @Description Leetcode 198. 打家劫舍 动态规划 中等难度
 * @Date 2021/10/9 21:32
 * @Version 1.0
 */
public class HouseRobber {


    /**
     * @param nums
     * @return
     */
    public int rob(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return nums[0];
        }

        //1.明确动态数组的定义
        int dp[] = new int[len + 1];

        //2.初始化条件
//        dp[0] = 1;

        //3.动态转移方程 的转移条件
        for (int i = 1; i <= len; i++) {

            //如果选择当前一个物资进行偷窃，则其值为前2
            if (i > 1) {
                dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
            } else {
                dp[i] = Math.max(nums[i - 1], dp[i - 1]);
            }


        }


        return dp[len];
    }


    public int rob1(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return nums[0];
        }

        //1.明确动态数组的定义
        int dp[] = new int[len + 1];

        //2.初始化条件
//        dp[0] = 1;

        //3.动态转移方程 的转移条件
        dp[1] = nums[0];
        for (int i = 2; i <= len; i++) {

            //如果选择当前一个物资进行偷窃，则其值为前2
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);


        }


        return dp[len];
    }


    public static void main(String[] args) {
        HouseRobber houseRobber = new HouseRobber();
        int[] nums = new int[]{2, 7, 9, 3, 1};

        int i = houseRobber.rob(nums);
        System.out.println(i);
    }
}
